/*
 * @lc app=leetcode.cn id=209 lang=cpp
 *
 * [209] 长度最小的子数组
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        vector<long long> dp(nums.size()+1, 0);
        for(int i = 0; i < nums.size(); i++)
            dp[i+1] = dp[i] + nums[i];

        if(*(dp.end() - 1) < target) return 0;
        
        //此时一定有符合条件的子数组
        int ans = dp.size();

        for(int i = 0, j = 1; j <= nums.size(); j++)
        {
            while(dp[j] - dp[i] >= target)
            {
                ans = min(ans, j - i);
                i++;
            }
        }


        return ans;
    }
};
// int main()
// {
//     vector<int> nums = {2,3,1,2,4,3};
//     Solution().minSubArrayLen(7, nums);
//     return 0;
// }
// @lc code=end

